package com.algorithm.learning.base.链表;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/20 21:42
 **/
public class 双链表实现双端队列 {

    public static class Node<V> {
        private V value;
        private Node<V> next;
        private Node<V> pre;

        public Node(V value) {
            this.value = value;
        }
    }

    public static class MyDequeue<V> {
        private int size;

        private Node<V> head;
        private Node<V> tail;

        public MyDequeue() {
            head = null;
            tail = null;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public void addFirst(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.pre = cur;
                head = cur;
            }
            size++;
        }

        public void addLast(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                tail.next = cur;
                cur.pre = tail;
                tail = cur;
            }
            size++;
        }

        public V pollFirst() {
            V ans = null;
            if (head == null) {
                tail = null;
                return ans;
            }
            ans = head.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.pre = null;
            }
            size--;
            return ans;
        }

        public V pollLast() {
            V ans = null;
            if (tail == null) {
                head = null;
                return ans;
            }
            ans = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.pre;
                tail.next = null;
            }
            size--;
            return ans;
        }
    }

    public static void main(String[] args) {
        MyDequeue<Integer> dequeue = new MyDequeue<>();
        dequeue.addFirst(1);
        dequeue.addFirst(2);
        dequeue.addFirst(3);
        dequeue.addFirst(4);
        while (!dequeue.isEmpty()) {
            System.out.println(dequeue.pollFirst());
        }

        dequeue.addFirst(1);
        dequeue.addFirst(2);
        dequeue.addFirst(3);
        dequeue.addFirst(4);
        while (!dequeue.isEmpty()) {
            System.out.println(dequeue.pollLast());
        }
    }
}
